public class HashBucket {
    class Node{
        public int key;
        public int value;
        public Node next;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    public Node[] array;
    public int usedSize;
    //默认负载因子为0.75
    public static final float DEFAULT_LOAD_FACTOR = 0.75f;
    public HashBucket() {
        this.array = new Node[10];
    }

    public  void put(int key, int val){
        Node node = new Node(key,val);
        int index = key % array.length;
        Node cur = array[index];
        //Map里面如果插入的元素的key与原本Map里面某个元素的key相同，此时会进行value的覆盖
        while (cur != null){
            if (cur.key == key){
                cur.value = val;
                return;//替换完成
            }
            cur = cur.next;
        }
        //将当前元素插入到当前array[index]所在的链表中去
        node.next = array[index];
        array[index] = node;
        usedSize++;
        //计算负载因子
        if (loadFactor() >= DEFAULT_LOAD_FACTOR){
            //扩容
            resize();
        }
    }
    private float loadFactor(){
        return usedSize*(1.0f) / array.length;
    }
    //扩容，需要重新哈希原来的数据，因为比如原来在4位置的14在扩容之后应当到扩容之后的14位置。
    private void resize(){
        Node[] tmparray = new Node[array.length * 2];
        for (int i = 0; i < array.length; i++) {
            Node cur = array[i];
            while (cur != null){
                Node curNext = cur.next;//用来存放原来array数组中当前位置节点的next节点，避免后面next变化了，使当前节点后面的节点全不见了
                int index = cur.key % tmparray.length;//计算当前节点在新数组中的位置
                cur.next = tmparray[index];//头插法
                tmparray[index] = cur;
                cur = curNext;//array位置的节点依次进行遍历
            }
        }
        array = tmparray;
    }
    //通过key值返回value
    public int get(int key){
        int index = key % array.length;//如果Key是一个字符串，比如说是一个person，此时就不能进行求余计算，需要使用hashcode将字符串转为整型
        Node cur = array[index];
        while (cur != null){
            if (cur.key == key){
                return cur.value;
            }
            cur = cur.next;
        }
        return -1;
    }
}
